1. Field of the Invention
The present invention relates to digital image processing and more specifically the compression of digital images by fractal coding.
2. Description of the Related Art
Fractal coding comprises searching, in a digital image, similar image portions to reduce the image volume by only, for the blocks considered as similar, coding a single block and identifying the other similar blocks by a reference to the first block.
FIG. 1 illustrates in a simplified view a digital image I in which a search window SW must be coded by fractal compression. The window is divided into blocks of same dimension, here B1, B2, . . . , B5, . . . , B9 of 32 by 32 pixels, search window SW being of 34 by 34 pixels. Blocks B1 to B9 overlap or cover one another in both directions. In practice, a search window of greater dimension is used, for example, 64 by 64 pixels. To simplify, an embodiment of the present invention will be described in relation with an example of a search window of 34 by 34 pixels. It however applies whatever the number of pixels of the search window and of the blocks.
The search for the similar blocks is performed with respect to a reference block also called range block RB of dimensions smaller than those of blocks B1 to B9. To enable comparison, blocks B1 to B9 are sub-sampled to obtain so-called domain blocks DB of same size as range block RB.
FIG. 2 illustrates this sub-sampling by a transformation of blocks Bi into domain blocks DBi. Each domain block contains values corresponding to the average pixel group values of the corresponding entire block.
The similarities between blocks RB and DB are not searched for identities only. It is also searched whether each domain block corresponds to the range block after given transformations. These transformations are called isometries and respectively correspond to a symmetry with respect to the vertical axis, a symmetry with respect to the horizontal axis, a 180° rotation, a symmetry of axis Y=X, a 270° rotation, a 90° rotation, and a symmetry of axis Y=−X.
The fractal image coding or compression technique is described, for example, in work “Fractal image compression: Theory and application to digital images” by Yuval Fisher, published by Springer Verlag, New-York, 1995. Another example of a fractal image compression algorithm is described in article “Design of an ASIC architecture for high speed fractal image compression” by Ancarani De Gloria and Olivieri Stazzone, published in IEEE “International ASIC conference”, September 1996.
Those skilled in the art can also refer to French patent application 2,775,812.
To enable comparing domain blocks with the range block, the range block and its seven isometries must conventionally be stored in distinct memory areas.